#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    string sortSentence(string s)
    {
        s.append(" ");
        int n = count(s.begin(), s.end(), ' ');
        vector<string> ans(n);
        int j = 0;
        for (size_t i = 0; i < s.length(); i++)
        {
            string word = "";
            if (' ' == s[i])
            {
                word = s.substr(j, i - j - 1);
                ans[s[i - 1] - '1'] = word;
                j = i + 1;
            }
        }
        auto join = [](const vector<string> &v, char c) -> string
        {
            string res = "";
            for (vector<string>::const_iterator p = v.begin();
                 p != v.end(); ++p)
            {
                res += *p;
                if (p != v.end() - 1)
                    res += c;
            }
            return res;
        };
        return join(ans, ' ');
    }

    string sortSentence_2(string s)
    {
        vector<string> res = vector<string>(9, "");
        int size = 0;
        int current = 0;
        for (int i = 0; i < s.length(); ++i)
        {
            if (s[i] >= '1' && s[i] <= '9')
            {
                int val = s[i] - '1';
                // current-i-1
                res[val] = string(s.begin() + current, s.begin() + (i));
                ++size;
                current = i + 2;
            }
        }
        string out;
        for (int i = 0; i < size; ++i)
        {
            out.append(res[i]);
            if (i != size - 1)
            {
                out.push_back(' ');
            }
        }
        return out;
    }
};
int main()
{
    Solution s;
    string str = "is2 sentence4 This1 a3";
    cout << s.sortSentence(str) << endl;
    return 0;
}